package ljl.alg.jianzhioffer.round3.medium;

import java.util.HashMap;
import java.util.Map;

public class _35_copyRandomList {

    static class Node {
        int val;
        Node next;
        Node random;

        public Node(int val) {
            this.val = val;
            this.next = null;
            this.random = null;
        }
    }

    class ai_wo_fuck_ju_ran_guo_le {

        Map<Node, Node> old2new = new HashMap<>();
        Map<Node, Node> old2random = new HashMap<>();
        public Node copyRandomList(Node head) {
            Node p = head;
            while (p != null) {
                Node newOne = new Node(p.val);
                old2new.put(p, newOne);
                old2random.put(p, p.random);
                p = p.next;
            }
            p = head;
            Node res = new Node(0);
            Node prev = res;
            while (p != null) {
                Node newOne = old2new.get(p);
                Node newRandom = old2random.get(p);
                if (newRandom != null) {
                    newRandom = old2new.get(newRandom);
                    newOne.random = newRandom;
                }
                prev.next = newOne;
                prev = newOne;
                p = p.next;
            }
            return res.next;
        }
    }

    class lufei {

        public Node copyRandomList(Node head) {
            Map<Node, Node> map = new HashMap<>();
            Node p = head;
            while (p != null) {
                map.put(p, new Node(p.val));
                p = p.next;
            }
            p = head;
            while (p != null) {
                Node new1 = map.get(p);
                new1.next = map.get(p.next);
                new1.random = map.get(p.random);
                p = p.next;
            }
            return map.get(head);
        }
    }

    class lufei3 {
        public Node copyRandomList(Node head) {
            if (head == null) return null;
            duplicate(head);
            linkRandom(head);
            return splitAndReturnNew(head);
        }

        void duplicate(Node head) {
            Node p = head;
            while (p != null) {
                Node n = new Node(p.val);
                n.next = p.next;
                p.next = n;
                p = n.next;
            }
        }

        void linkRandom(Node head) {
            Node p = head;
            while (p != null) {
                if (p.random != null) {
                    p.next.random = p.random.next;
                }
                p = p.next.next;
            }
        }

        Node splitAndReturnNew(Node head) {
            Node res = head.next;
            Node p = head.next;
            Node pre = head;
            while (p.next != null) {
                pre.next = pre.next.next;
                p.next = p.next.next;
                pre = pre.next;
                p = p.next;
            }
            pre.next = null;
            return res;
        }
    }

}
